package com.algorithm.learning.base.二叉树;

import java.util.Stack;

/**
 * @program: algorithm-learning
 * @description:
 * @author: YuKai Fan
 * @create: 2024/8/26 21:09
 **/
public class 非递归实现先序中序后序遍历 {

    /**
     * 利用栈来实现 先序遍历，只需要记住规则即可
     * 1、根节点先入栈，然后就弹出，并打印
     * 2、如果有右节点，则先压右节点；如果有左节点，则在压左节点；
     * 3、然后重复1，,2步骤
     * @param root
     */
    public static void preOrder(TreeNode root) {
        System.out.println("pre-order:");
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            System.out.print(node.value + " ");
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
    }

    /**
     * 后续遍历比较容易，根据先序遍历的规则，先压右节点，再压左节点，然后弹出，然后打印
     * 那么结果就是，头左右；
     *
     * 但是如果我们先压左节点，在压右节点，那么结果就是，头右左
     * 我们把这个结果，逆序就是左右头，也就是后续遍历
     *
     * 那么如果我们要打印结果，我们可以先把出栈的节点，不打印，而是先压入另外一个栈，等全部遍历完成后，在打印另一个栈的结果即可
     * @param root
     */
    public static void postOrder(TreeNode root) {
        System.out.println("post-order:");
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        // 这个栈只是存储结果的
        Stack<Integer> stack2 = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            stack2.push(node.value);
            if (node.left != null) {
                stack.push(node.left);
            }
            if (node.right != null) {
                stack.push(node.right);
            }
        }
        while (!stack2.isEmpty()) {
            System.out.print(stack2.pop() + " ");
        }
    }

    /**
     * 中序遍历的过程，还是需要栈来实现
     * 步骤如下：
     *
     * 1、先直接把整个树的左边界，压入栈中，如果左边界已经为空了，然后再弹出并打印
     * 2、当步骤1无法继续时，则返回弹出节点的右树上，继续执行步骤1
     * @param root
     */
    public static void inOrder(TreeNode root) {
        System.out.println("in-order:");
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || root != null) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                root = stack.pop();
                System.out.print(root.value + " ");
                root = root.right;
            }
        }
    }
}
